#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=6*1e3+10;

int f[N];
int sz[N];
struct node{
	int a,b,w;
	bool operator<(struct node& p1)
	{
		return w<p1.w;
	}
};

int Find(int x)
{
	if(f[x]!=x)
		f[x]=Find(f[x]);
	return f[x];
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		vector<node> edge;
		int n;
		cin>>n;
		for(int i=0;i<=n;i++)
			f[i]=i,sz[i]=1;
		for(int i=0;i<n-1;i++)
		{
			int x,y,z;
			cin>>x>>y>>z;
			edge.push_back({x,y,z});
		}
		sort(edge.begin(),edge.end());
		int ret=0;
		for(int i=0;i<edge.size();i++)
		{
			int x,y,z;
			x=edge[i].a,y=edge[i].b,z=edge[i].w;
			x=Find(x),y=Find(y);
			if(x!=y)
			{
				ret+=(sz[x]*sz[y]-1)*(z+1);
				sz[y]+=sz[x];
				f[x]=y;
			}
		}
		cout<<ret<<endl;
	}
	return 0;
}
